// ------------------------------------------------------------------------------------------------
// ---- Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein) ------------------------------------
// ---- Algoritmos de Seleção linear no Caso Médio e no Pior Caso (Capítulo 9) --------------------
// ------------------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>

#include <stdbool.h>// bool,false,true
#include <time.h>   // time_t,time,difftime
#include <math.h>   // floor
#include <windows.h>// GetTickCount

int Selecao(int* A, int p, int r, int k);
int Selecao_aleat(int* vetor, int p, int r, int k);


void InsertionSort(int* vetor, int p, int r);
void HeapSort(int* vetor, int p, int r);


void imprimir_vetor(int* vetor, int N, char* filename);


int main() {
    int i,j;

    // Cria um vetor
    int N = 10000000;
    int* vetor = (int*) calloc(N,sizeof(int));
    srand (time(NULL));
    for (i=0;i<N;i++) vetor[i] = rand()%10000;

    //imprimir_vetor(vetor,N,"entrada.txt");
    int k =  N/2;
    int t1 = GetTickCount();

    int valor0 = Selecao(vetor,0,N-1,k);
    int t2 = GetTickCount();

    int valor1 = Selecao_aleat(vetor,0,N-1,k);
    int t3 = GetTickCount();


    HeapSort(vetor, 0, N-1);
    int valor2 = vetor[k-1];
    imprimir_vetor(vetor,N,"saida.txt");

    printf("Valor0 = %d/ Valor1 = %d/ Valor2 = %d\nTempo0= %d miliseg/ Tempo1 = %d miliseg\n",valor0,valor1,valor2,t2-t1,t3-t2);
    free(vetor);
    return 0;
}



// ------------------------------------------------------------------------------------------------
// ---- Algoritmo PARTICIONE ----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void trocar(int* x, int* y) {int z = (*x); (*x) = (*y); (*y) = z;}

int Particione_original(int* vetor, int p, int r) {
    int pivo = vetor[r];
    int j, i=p-1;
    for (j=p; j<r; j++) {
        if (vetor[j] <= pivo) {
            i++;
            trocar(&vetor[i], &vetor[j]);
        }
    }
    trocar(&vetor[i+1], &vetor[r]);
    return i+1;
}

int Particione_aleat(int* vetor, int p, int r) {
    srand (time(NULL));
    int pos_pivo = p + rand()%(r-p+1);
    trocar(&vetor[pos_pivo], &vetor[r]);
    return Particione_original(vetor,p,r);
}

int Particione(int* vetor, int p, int r, int pivo) {
    int j, i=p-1;
    for (j=p; j<r; j++) {
        if (vetor[j] < pivo) {
            i++;
            trocar(&vetor[i], &vetor[j]);
        } else if (vetor[j]==pivo) {
            trocar(&vetor[j], &vetor[r]);
            break;
        }
    }
    for (j=j; j<r; j++) {
        if (vetor[j] <= pivo) {
            i++;
            trocar(&vetor[i], &vetor[j]);
        }
    }
    trocar(&vetor[i+1], &vetor[r]);
    return i+1;
}

// ------------------------------------------------------------------------------------------------
// ---- Algoritmo SELECAO -------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
int Selecao_aleat(int* A, int p, int r, int k) {
    if (p==r) return A[p];
    int q = Particione_aleat(A,p,r);
    int i = q-p+1;
    if (k==i) return A[q];
    if (k<i) return Selecao_aleat(A,p,q-1,k);
    return Selecao_aleat(A,q+1,r,k-i);
}



int Selecao(int* A, int p, int r, int k) {
    int i, N=r-p+1;
    if (N<10) {
        if (k>N) k=N;
        InsertionSort(A,p,r);
        return A[p+k-1];
    }

    int tam_M = N/5;
    int* M = (int*) calloc(tam_M,sizeof(int));
    for (i=0; i<tam_M; i++) {
        InsertionSort(A, p+5*i, p+5*i+4);
        M[i] = A[p+5*i+2];
    }

    int pivo = Selecao(M, 0, tam_M-1, tam_M/2);
    free(M);

    int q = Particione(A, p, r, pivo);
    i = q-p+1;
    if (k==i) return A[q];
    if (k<i) return Selecao(A,p,q-1,k);
    return Selecao(A,q+1,r,k-i);
}


// ------------------------------------------------------------------------------------------------
// ---- Algoritmo INSERTIONSORT -------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void InsertionSort(int* vetor, int p, int r) {
    int i,j,carta;
    for (j=p+1;j<=r;j++) {
        carta = vetor[j];
        i = j-1;
        while ((i>=p)&&(vetor[i]>carta)) {
            vetor[i+1] = vetor[i];
            i--;
        }
        vetor[i+1] = carta;
    }
}


// ------------------------------------------------------------------------------------------------
// ---- Algoritmo HEAPSORT ------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void maxheapify(int* vetor, int i, int p, int r) {
    int m = i;
    int esq = p+2*(i-p)+1;
    int dir = p+2*(i-p)+2;
    if ((esq<r)&&(vetor[esq]>vetor[i])) m = esq;
    if ((dir<r)&&(vetor[dir]>vetor[m])) m = dir;
    if (m != i) {
        trocar(&vetor[i], &vetor[m]);
        maxheapify(vetor,m,p,r);
    }
}

void HeapSort(int* vetor, int p, int r) {
    int i;
    for (i=(r+p-1)/2; i>=p; i--) {
        maxheapify(vetor,i,p,r);
    }
    for (i=r;i>p;i--) {
        trocar(&vetor[p], &vetor[i]);
        r = r-1;
        maxheapify(vetor,p,p,r);
    }
}


// ------------------------------------------------------------------------------------------------
// ---- Imprimir vetor em arquivo -----------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void imprimir_vetor(int* vetor, int N, char* filename) {
    if (filename==NULL) filename="saida.txt";
	FILE* arq = fopen(filename,"w");
	int i;
    for (i=0;i<N;i++) fprintf(arq,"%d ",vetor[i]);
	fclose(arq);
}